COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	\magnification\magstephalf
C00009 ENDMK
C⊗;
\magnification\magstephalf
\input macro.tex
\def\today{\ifcase\month\or
  January\or February\or March\or April\or May\or June\or
  July\or August\or September\or October\or November\or December\fi
  \space\number\day, \number\year}
\baselineskip 14pt
\rm
\line{\sevenrm a45.tex[154,phy] \today\hfill}

\bigskip
\line{\bf Ambiguity\hfil}

A grammar is defined to be {\sl ambiguous\/} if there is a sentence with
more than one derivation tree. Notice that distinct derivation trees may
correspond to a single derivation:
$$\vcenter{\halign{$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad\qquad\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\qquad
&$\hfil#\hfil$\cr
&&E&&&E\cr
\noalign{\bigskip}
&E&+&E&E&+&E\cr
\noalign{\bigskip}
E&+&E&z&x&E&+&E\cr
\noalign{\bigskip}
x&&y&&&y&&z\cr}}$$
{}
$$\vcenter{\halign{$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\cr
&&E\cr
&E&+&E\cr
E&+&E&+&E\cr
x&+&E&+&E\cr
x&+&y&+&E\cr
x&+&y&+&z\cr}}$$
unless the derivation marks the variable being rewritten:
$$\vcenter{\halign{$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\qquad\qquad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\cr
&&\underline{E}&&&&&\underline{E}\cr
&\underline{E}&+&E&&&E&+&\underline{E}\cr
\underline{E}&+&E&+&E&\underline{E}&+&E&+&E\cr
&&\hbox{etc.}&&&&&\hbox{etc.}\cr}}$$

\noindent
Notice also that there may be sentential forms with more than one derivation
tree, that derive no sentences:

$$\vcenter{\halign{$#\hfil$\qquad\qquad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\qquad\qquad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\quad
&$\hfil#\hfil$\cr
&&&S&&&S\cr
\noalign{\bigskip}
S→A\mid b&&&A&&&A\cr
\noalign{\bigskip}
A→AA&&A&&A&A&&A\cr
\noalign{\bigskip}
&A&&A&&&A&&A\cr}}$$

\bigskip
A sentence has as many derivation trees as it has leftmost derivations.
{\bf Drill:} Prove it.
Therefore, a sentence is ambiguous iff it has more than one leftmost derivation.
A~CFG is ambiguous if it has ambiguous sentences. A~CFL is inherently
ambiguous if every grammar for it is ambiguous.

\disleft 38pt::
{\bf Exercise:} 
Find an algorithm to transform an unambiguous CFG into an unambiguous CNF
grammar.

In a derivation tree for sentence $uvw$, $v$~is a {\sl phrase\/} if it is
the yield of a subtree. In a leftmost derivation, $v$~is a phrase if the
derivation goes $S\aRa uA\beta\aRa uv\beta\aRa uvw$. [This is a slight
misstatement. 
{\bf Drill:} In what way?]
The phrases in a derivation are nested; if two phrases overlap
at all, one contains the other. 
{\bf Drill:} Prove it.
Therefore, if $x$ is a phrase in 
derivation tree~$T↓1$, $y$~is a phrase in derivation tree~$T↓2$, and
$x$ overlaps~$y$ without inclusion, then the derivation trees are
different, and the sentence derived is ambiguous. This gives a way to
show inherent ambiguity of a language: show that for any grammar of~$L$,
there is a sentence with such overlapping substrings $x$ and~$y$, where
each is a phrase in some derivation.

\proclaim Theorem. A DPDL has an unambiguous grammar.

\noindent{\bf Proof.} Convert the DPDM to clean form; it remains deterministic.
Construct a~CFG by the standard method. Show that a computation of the PDM
uniquely determines a derivation tree for the CFG, so ambiguity of the
grammar would imply nondeterminism for the PDM.

This gives a method to show that a language is not inherently ambiguous:
Find a DPDM recognizer for it. The converse does not hold:
$a↑ib↑ic\cup a↑ib↑{2i}d$ is not a DPDL, but is unambiguous.



\bigskip
\parindent0pt
\copyright 1986 Robert W. Floyd.
First draft (not published)
May 12, 1986.
%revised date;
%subsequently revised.

\bye